#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>

int show(int *a, int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

int cmp(const void *a, const void *b)
{
    return *(int *) a - *(int *) b;
}

int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes)
{
    qsort(nums, numsSize, sizeof(int), cmp);

    int **result = (int **) malloc(6 * (numsSize + 1) * sizeof(int *));
    int *resultCol = (int *) malloc(6 * (numsSize + 1) * sizeof(int));
    int resultSize = 0;

    for (int i = 0; i < numsSize - 2; i++) {
        int left = i + 1;
        int right = numsSize - 1;

        if (nums[i] > 0) {
            break;
        }

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result[resultSize] = (int *) malloc(3 * sizeof(int));
                result[resultSize][0] = nums[i];
                result[resultSize][1] = nums[left];
                result[resultSize][2] = nums[right];
                resultCol[resultSize] = 3;
                resultSize++;

                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            }
        }
    }

    *returnSize = resultSize;
    *returnColumnSizes = resultCol;
    return result;
}

int main(int argc, char const *argv[])
{
    int nums[] = { -1, 0, 1, 2, -1, -4 };
    // int nums[] = { 0, 0, 0 };
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize = 0;
    int *colSize = NULL;
    int **result = threeSum(nums, numsSize, &returnSize, &colSize);

    for (int i = 0; i < returnSize; i++) {
        show(result[i], colSize[i]);
    }

    for (int i = 0; i < returnSize; i++) {
        free(result[i]);
    }
    free(result);
    free(colSize);

    return 0;
}